The present invention describes a logic for multilevel secure databases. By using such logic not only can multilevel databases be formalized, the proof procedures can be used to process security constraints efficiently and subsequently control inferences in multilevel secure database management systems. The motivation for this work is given below. The teachings of the references cited in this specification are herein incorporated by reference.
Database management systems have for some time used mathematical logic as their conceptual framework. Current database management systems are involved in complex deduction and decision-making processes, encouraging further development of logic programming for increasingly powerful and intelligent database management systems. See Cohen, B., 1989, "Merging Expert Systems and Database Systems," AI-EXPERT, Vol. 2, No. 2; "ICOT Project," 1987, New Generation Computing Journal, Vol. 5; and Gallaire, H., and J. Minker, 1978, Logic and Databases, Plenum Press, New York.
While logic programming researchers were making significant progress in the area of logic and databases, Gallaire, H., and J. Minker, 1978, Logic and Databases, Plenum Press, New York; Reiter, R., 1978, "On Closed-World Databases," (Editors: H. Gallaire and J. Minker), Logic and Databases, New York: Plenum Press; Clark, K., (Editors: H. Gallaire and J. Minker), 1978, "Negation as Failure," Logic and Databases, Plenum Press, New York; Kowalski, R. A. (Editors: H. Gallaire and J. Minker), 1978, "Logic for Data Description," Logic and Databases, New York: Plenum Press; Nicolas, J., and K. Yazdania, (Editors: H. Gallaire and J. Minker), 1978, "Integrity Checking in Deductive Databases," Logic and Databases, New York: Plenum Press; Lloyd, J., 1987, Foundations of Logic Programming, (2nd Edition), Heidelberg, Germany: Springer Verlag; and Minker, J., 1988, Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, the security researchers contributed towards the design and development of multilevel-secure relational database management systems. In such database systems, the users cleared at different security levels can access and share a database with data at different sensitivity levels without violating security, Hinke, T. and M. Schaefer, November 1975, Secure Data Management System, RADC-TR-75-266, System Development Corporation; Grohn, M., 1976, A Model of a Protected Data Management System, ESD-TR-76-289, Ottawa, Canada: I. P. Sharp Associates Limited; Graubart, R. D., and J. P. L. Woodward, April 1982, "A Preliminary Naval Surveillance DBMS Security Model," Proceedings of the 1982 IEEE Symposium on Security and Privacy, Oakland, Calif.; Graubart, R. D., and K. Duffy, April 1985 "Design Overview for Retrofitting Integrity-Lock Architecture onto a Commercial DBMS," Proceedings of the 1985 Symposium on Security and Privacy, Oakland, Calif.; Denning, D. E., at al., April 1987, "A Multilevel Relational Data Model," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif.; O'Conner, J. and J. Gray, October 1988, "Query Processing in a Secure Distributed Architecture," Proceedings of the 11th National Computer Security Conference, Baltimore, Md.; Garvey, C., and A. Wu, April 1988, "ASD-Views," Proceedings of the 1988 IEEE Symposium on Security and Privacy, Oakland, Calif.; Stachour, P., M. B. Thuraisingham, and P. Dwyer, October 1988, "Update Processing in LDV--A Secure Database Management System," Presented at the 11th National Computer Security Conference, Baltimore, Md.; and Thuraisingham, M. B., 1989, "Towards the Design of a Secure Data/Knowledge Base Management System," Accepted for Publication in Data and Knowledge Engineering Journal. Despite all these advances in multilevel databases, a logic for reasoning in a multilevel environment or a logic programming system for multilevel environments does not exist at present. As a result, the multilevel data/knowledge base management systems lack several features that have been successfully incorporated into the traditional data/knowledge base management systems. These include constraint processing, deductive reasoning, and handling efficient proof procedures.
An early attempt was made to view multilevel databases through first-order logic, Thuraisingham, M. B., (Editor: T. Lunt), May 1988, "Foundations of Multilevel Databases," Presented at the 1st RADC Database Security Invitational Workshop, Menlo Park, Calif. (Proceedings published by Springer Verlag, Heidelberg, Germany). Although not entirely successful, this approach helped gain an insight into utilizing formal logic to develop multilevel systems. That is, classical first order logic, being monotonic, was found to be an inappropriate tool for formalizing concepts in multilevel databases. This is because it is possible for users at different security levels to have different views of the same entity. In other words, statements that are assumed to be true at one security level can very well be false at a different security level. In other words, the universe in a multilevel environment is decomposed into multiple-worlds, one for each security level. A Nonmonotonic Typed Multilevel Logic (NTML) for reasoning in multilevel environments is disclosed in this specification.
The invention extends typed first order logic to support a multilevel environment. In this disclosure we introduce the development of NTML. In addition, the disclosure describes our research on various related topics that are essential for the development of successful multilevel intelligent data/knowledge base management systems. These include (1) viewing multilevel databases through NTML, (2) developing the essential points of a logic programming language for multilevel systems based on NTML, (3) designing techniques for security/integrity constraint processing for multilevel secure database management systems, and (4) proposing extensions to NTML in order to support reasoning in the midst of uncertain nonmonotonic, incomplete, precise and imperfect knowledge.